package com.datastructure.list;

public class JosepFu {
    public static void main(String[] args) {
        CycleLinkedList cycleLinkedList = new CycleLinkedList(5);
        cycleLinkedList.show();
        cycleLinkedList.solveJospFu(3,3);
    }
}

class CycleLinkedList {
    NumNode first;
    CycleLinkedList(int totalNum) {
        if (totalNum < 1) {
            System.out.println("totalNum < 1,创建失败");
            return;
        }
        //定义首节点
        first = new NumNode(1);
        first.next = first;
        //其他节点
        NumNode curNode =first;
        for (int i=2; i <= totalNum; ++i) {
            NumNode node = new NumNode(i);
            curNode.next = node;
            node.next = first;
            curNode = curNode.next;
        }
    }
    public void show() {
        if (first == null) {
            System.out.println("环形链表为空");
        }
        NumNode curNode = first;
        do {
            System.out.println("节点编号: " + curNode.num);
            curNode = curNode.next;
        } while (curNode != first);
    }

    /**
     *
     * @param startNum 从第几个节点开始报数
     * @param countNum 数几下 countNum
     */
    public void solveJospFu(int startNum,int countNum) {
        if (first == null) {
            return;
        }
        NumNode lastNode = lastNode(first); //辅助节点删除操作

        //将first移动到开始报数的位置
        while (startNum > 1) { //
            lastNode = lastNode.next;
            first = first.next;
            --startNum;
        }

        //
        while (first != lastNode) { //只有一个节点时退出
            int mCountNum = countNum;
            while (mCountNum > 1) { //开始报数，数 countNum下
                lastNode = lastNode.next;
                first = first.next;
                --mCountNum;
            }
            //此时要删除的节点就是 first
            System.out.print("移除节点：" + first.num);
            lastNode.next = first.next;
            first = first.next;
            System.out.println(", 当前链表为：");
            show();
        }

    }

    /**
     * 找到 first 节点的前一个节点
     * @param first 第一个节点
     * @return first 节点的前一个节点
     */
    private NumNode lastNode(NumNode first) {
        NumNode curNode = first; //辅助遍历
        while(curNode.next != first) { //next == first 时就是目标节点
            curNode = curNode.next;
        }
        return curNode;
    }

}
class NumNode {
    int num; //节点序号
    NumNode next;
    NumNode(int num) {
        this.num = num;
        this.next = null;
    }
}